%\documentclass{llncs}
\documentclass[11pt]{article}
%\usepackage{makeidx}


\usepackage{times}
\usepackage[small,compact]{titlesec}
\usepackage[small,it]{caption}

\usepackage{fullpage}

%\usepackage{times}

\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{epsfig}
\usepackage{pstricks, pst-node}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{amsthm}


\newcommand{\squishlist}{
 \begin{list}{$\bullet$}
  { \setlength{\itemsep}{0pt}
     \setlength{\parsep}{3pt}
     \setlength{\topsep}{3pt}
     \setlength{\partopsep}{0pt}
     \setlength{\leftmargin}{1.5em}
     \setlength{\labelwidth}{1em}
     \setlength{\labelsep}{0.5em} } }

\newcommand{\squishlisttwo}{
 \begin{list}{$\bullet$}
  { \setlength{\itemsep}{0pt}
     \setlength{\parsep}{0pt}
    \setlength{\topsep}{0pt}
    \setlength{\partopsep}{0pt}
    \setlength{\leftmargin}{2em}
    \setlength{\labelwidth}{1.5em}
    \setlength{\labelsep}{0.5em} } }

\newcommand{\squishend}{
  \end{list}  }


\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
%%\newtheorem{theorem}{Theorem}
%%\newtheorem{lem}{Lemma}
%%\newtheorem{proposition}{Proposition}
%%\newtheorem{claim}{Claim}
%%\newtheorem{fact}{Fact}
%%\newtheorem{corollary}{Corollary}
\newtheorem{definition}{Definition}
%%\newenvironment{pf}{{\bf Proof:}}{\hfill\rule{1.5mm}{3mm}\vspace{0.1in}}

\newtheorem{invariant}{Invariant}

%\newcommand{\pr}{{\mathbf{Pr}}}
%\newcommand{\E}{{\mathbf E}}
%
%\newcommand{\pr}{{\mathrm Pr}}
%
%\newcommand{\sbinom}[2]{\left( \stackrel{{#1}}{_{#2}} \right)}
%
%\newcommand{\nchoosetwo}{\sbinom{n}{2}}
%
\newcommand{\integer}{{\mathbb Z}}
\newcommand{\real}{{\mathbb R}}
%
\newcommand{\pname}[1]{{\sc #1}}
%
\newcommand{\comment}[1]{}
%
\newcommand{\figframe}[3]{
\begin{figure}
\begin{center}
\fbox{
\begin{minipage}[t]{#1}
#2
\end{minipage}
}
\end{center}
#3
\end{figure}
}
%
%\long\def\symbolfootnotetext[#1]#2{\begingroup%
%\def\thefootnote{\fnsymbol{footnote}}\footnotetext[#1]{#2}\endgroup}
%
%\pagestyle{plain}
%\usepackage{fullpage}
%\newcommand{\delete}[1]{}
\def\polylog{\operatorname{polylog}}
\def\cf{{\em cf.}}

\begin{document}
\title{5.24-approximation Semi-Streaming Algorithm for Weighted Maximum
Matching}
%\titlerunning{5.24-approximation Matching on Semi-Stream}

\author{Atish Das Sarma \and Richard J. Lipton \and
Danupon Nanongkai \thanks{Georgia Institute of Technology,
email: {\tt \{atish, rjl, danupon\}@cc.gatech.edu}}}
                                         
\date{}

\maketitle

% the abstract has to PRECEDE the command \maketitle:
% be sure not to issue the \maketitle command twice!
\begin{abstract}
\noindent We consider the maximum weight matching problem in the
one-pass semi-streaming setting. In this setting, only
$O(n\polylog{n})$ bits of memory is allowed where $n$ is the number
of vertices. We improve the best known approximation ratio from
5.585 by Zelke [STACS'08] to 5.24 by presenting a new algorithm {\sc GlobalShadowMatching}.
%
%We show that a modification of Zelke's algorithm [STACS'08] admit a
%5.45 approximation ratio
%
%for a single machine have been developed, improving the
%approximation guarantee from 6 to 5.58 over papers~\cite{FKMSZ05,
%McGregor05, Zelke08}. We show that a slight modification of Zelke's
%algorithm~\cite{Zelke08} improves the approximation guarantee from
%5.58 to 4.62.
\end{abstract}

% start the paper here:
\input{intro}
\input{algo}
\input{analysis_overview}
\input{simplification}
\input{charging_scheme}
\input{invariant_proofs}
\input{conclusion}


  \let\oldthebibliography=\thebibliography
  \let\endoldthebibliography=\endthebibliography
  \renewenvironment{thebibliography}[1]{%
    \begin{oldthebibliography}{#1}%
      \setlength{\parskip}{0ex}%
      \setlength{\itemsep}{0ex}%
  }%
  {%
    \end{oldthebibliography}%
  }
{
\bibliographystyle{plain}
%\bibliographystyle{alpha}
\bibliography{matching}
}



%\bibliographystyle{plain}
%\bibliographystyle{splncs}
%\bibliography{matching}

\newpage
\appendix
\input{appendix}

%\newpage\appendix

\end{document}
